package 每日一题;

import com.alibaba.fastjson.JSON;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class No995K连续位的最小翻转次数 {

    /**
     * 在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
     * 返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
     *
     * 示例 1：
     * 输入：A = [0,1,0], K = 1
     * 输出：2
     * 解释：先翻转 A[0]，然后翻转 A[2]。
     * 示例 2：
     * 输入：A = [1,1,0], K = 2
     * 输出：-1
     * 解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
     * 示例 3：
     * 输入：A = [0,0,0,1,0,1,1,0], K = 3
     * 输出：3
     * 解释：
     * 翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
     * 翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
     * 翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
     *
     * 提示：
     * 1 <= A.length <= 30000
     * 1 <= K <= A.length
     */

    //超时的题解,中间改变数组的for太过于冗余,导致了超时。 参考解法:不要进行真正的翻转
    public int minKBitFlips(int[] A, int K) {

        //貌似找到了规律,贪心,总是从0开始向右
        int count=0;
        int index=0;

        while (index+K<=A.length){

            while (index<A.length&&A[index]!=0){
                index++;
            }
            if(index==A.length){
                break;
            }
            Integer tempIndex=null;
            int leftStart= index;
            System.out.println(JSON.toJSONString(A));
            //这里复杂度较高,有无用的操作,导致了超时
            for (; index < leftStart+K && leftStart+K<=A.length; index++) {
                if(A[index]==0){
                    A[index]=1;
                }else{
                    A[index]=0;
                    //记录第一次出现index的下标
                    tempIndex=(tempIndex==null?index:tempIndex);
                }
            }
            System.out.println(JSON.toJSONString(A));
            count++;
            if(tempIndex!=null){
                index=tempIndex;//有就回序
            }

        }

        for (int i = A.length-1; i >=A.length-K ; i--) {
            if(A[i]==0){
                return -1;
            }
        }

        return count;
    }

    public int minKBitFlipsGood(int[] A, int K) {
        int count=0;
        Deque<Integer> queue=new ArrayDeque<>();
        for (int i = 0; i < A.length; i++) {

            //不相关的下标出列
            if(!queue.isEmpty()&&queue.getFirst()+K<=i){
                queue.removeFirst();
            }

            //下面要变就是不符合的
            if(queue.size()%2==0&&A[i]==0){

                //这里在变,长度就不够了
                if(i+K>A.length){
                    return -1;
                }

                //队列偶数个对0 要变
                queue.addLast(i);
                count++;
            }else if(queue.size()%2==1&&A[i]==1){

                //这里在变,长度就不够了
                if(i+K>A.length){
                    return -1;
                }

                //队列奇数个对1 要变
                queue.addLast(i);
                count++;
            }

        }

        return count;
    }

    public static void main(String[] args) {
        No995K连续位的最小翻转次数 n=new No995K连续位的最小翻转次数();
        int[] arr={1,0,0,1};
        int result = n.minKBitFlipsGood(arr, 1);
        System.out.println(result);
    }

}
